/*
ID: pallab81
PROG:
LANG: C++
*/

//"I have not failed, I have just found 10000 ways that won't work.

#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>
#include <iomanip>

#include <ctime>
#include <cassert>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <cstring>
#include <cstdlib>

using namespace std;

#define VI vector< int >
#define CI( x ) scanf("%d",&x)
#define CL( x ) scanf("%lld",&x)
#define CD( x ) scanf("%lf",&x )
#define foR(i,st,ed) for(int i = st ; i < ed ; ++i )
#define fo(i,ed) foR( i , 0 , ed )
#define foE(i,st,ed) for(int i = st ; i <= ed ; ++i )
#define foit(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
#define bip system("pause")
#define Int long long
#define pb push_back
#define SZ(X) (int)(X).size()
#define LN(X) (int)(X).length()
#define mk make_pair
#define f first
#define s second
#define SET( ARRAY , VALUE ) memset( ARRAY , VALUE , sizeof(ARRAY) )

class CheapestRoute {
public:
    vector <int> routePrice(vector <int> cellPrice, vector <int> enterCell, vector <int> exitCell, int teleportPrice);
};
vector< int > cp; // cost to enter into ith cell
vector< vector<int> > E;
int tcost; // cost of using a teliport
int dp1[50+2][50+2][50+2];
int dp2[50+2][50+2][50+2];
int V;

int f1(int cur_port, int cur_teli, int tt) {
    if ( cur_port+1 ==SZ(cp) ) {
        return 0;
    }

    int& best = dp1[cur_port][cur_teli][tt];
    if ( best!=-1 ) {
        return best;
    }

    best = (int)1023456789;
    // samne jaite pari
    if ( cur_port+1 < SZ(cp) && cp[cur_port+1]!=-1 && tt+1 <=51 ) {
        int v1 = cp[cur_port+1]+f1(cur_port+1, cur_teli,tt+1);
        best = min( best, v1 );
    }
    // pichone jaite pari
    if ( cur_port-1 >= 0 && cp[cur_port-1]!=-1  && tt+1 <=51 ) {
        int v1 = cp[cur_port-1]+f1(cur_port-1, cur_teli, tt+1);
        best = min( best, v1 );
    }

    // teliport use kore
    for (int i=0,j=SZ( E[cur_port] ); i<j; ++i ) {
        int v = E[cur_port][i];
        if ( cp[v]!=-1 && tt+1 <=51 ) {
            int v1 = (tcost+cur_teli)+f1(v,cur_teli+1, tt+1);
            best = min( best, v1 );
        }
    }

    return best;
}
int f2(int p,int t,int m) {
    if (p+1==SZ(cp)) {
        return 0;
    }

    int &best = dp2[p][t][m];
    if ( best!=-1 ) {
        return best;
    }
    best = (int)1023456789;
    // samne giye
    if ( p+1 < SZ(cp) && cp[p+1]!=-1 && m+1 <=51  ) {

        if ( f1(p,t,m)== cp[p+1]+f1(p+1,t,m+1) ) {
            int v1 = 1+f2(p+1,t,m+1);
            best = min(best,v1);
        }

    }

    //pichone giye
    if ( p-1>=0 && cp[p-1]!=-1 && m+1 <= 51 ) {

        if ( f1(p,t,m)==cp[p-1]+f1(p-1,t,m+1) ) {
            int v1 = 1+f2(p-1,t,m+1);
            best = min(best, v1);
        }
    }
    
    //teliport use kore
    for (int i=0,j=SZ(E[p]); i<j; ++i ) {
        int v = E[p][i];
        if ( cp[v]!=-1 && m+1 <=51 ) {

            if ( f1(p,t,m)== tcost+t+f1(v,t+1,m+1) ) {
                int v1 = 1+f2(v,t+1,m+1);
                best = min( best, v1 );
            }
        }
    }
    return best;
}

vector <int> CheapestRoute :: routePrice(vector <int> cellPrice, vector <int> enterCell, vector <int> exitCell, int teleportPrice) {
    vector <int> retval;
    cp.clear();
    cp = cellPrice;
    tcost = teleportPrice;

    E.assign(52,vector<int>());
    for (int i=0,j=SZ(enterCell); i<j; ++i ) {
        E[ enterCell[i] ].pb( exitCell[i] );
    }

    SET(dp1,-1);
    V = f1(0,0,0);
    if ( V>=(int)1023456789 ) {
        return retval;
    }
    retval.assign(2,0);
    SET(dp2,-1);

    retval[0]=V;
    retval[1]=f2(0,0,0);
    //  printf("MINIMUM COST > %3d , %3d\n",retval[0],retval[1]);

    return retval;
}
// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit 2.1.8 (beta) modified by pivanof
#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool KawigiEdit_RunTest(int testNum, vector <int> p0, vector <int> p1, vector <int> p2, int p3, bool hasAnswer, vector <int> p4) {
    cout << "Test " << testNum << ": [" << "{";
    for (int i = 0; int(p0.size()) > i; ++i) {
        if (i > 0) {
            cout << ",";
        }
        cout << p0[i];
    }
    cout << "}" << "," << "{";
    for (int i = 0; int(p1.size()) > i; ++i) {
        if (i > 0) {
            cout << ",";
        }
        cout << p1[i];
    }
    cout << "}" << "," << "{";
    for (int i = 0; int(p2.size()) > i; ++i) {
        if (i > 0) {
            cout << ",";
        }
        cout << p2[i];
    }
    cout << "}" << "," << p3;
    cout << "]" << endl;
    CheapestRoute *obj;
    vector <int> answer;
    obj = new CheapestRoute();
    clock_t startTime = clock();
    answer = obj->routePrice(p0, p1, p2, p3);
    clock_t endTime = clock();
    delete obj;
    bool res;
    res = true;
    cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
    if (hasAnswer) {
        cout << "Desired answer:" << endl;
        cout << "\t" << "{";
        for (int i = 0; int(p4.size()) > i; ++i) {
            if (i > 0) {
                cout << ",";
            }
            cout << p4[i];
        }
        cout << "}" << endl;
    }
    cout << "Your answer:" << endl;
    cout << "\t" << "{";
    for (int i = 0; int(answer.size()) > i; ++i) {
        if (i > 0) {
            cout << ",";
        }
        cout << answer[i];
    }
    cout << "}" << endl;
    if (hasAnswer) {
        if (answer.size() != p4.size()) {
            res = false;
        } else {
            for (int i = 0; int(answer.size()) > i; ++i) {
                if (answer[i] != p4[i]) {
                    res = false;
                }
            }
        }
    }
    if (!res) {
        cout << "DOESN'T MATCH!!!!" << endl;
    } else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2) {
        cout << "FAIL the timeout" << endl;
        res = false;
    } else if (hasAnswer) {
        cout << "Match :-)" << endl;
    } else {
        cout << "OK, but is it right?" << endl;
    }
    cout << "" << endl;
    return res;
}
int main() {
    bool all_right;
    all_right = true;

    vector <int> p0;
    vector <int> p1;
    vector <int> p2;
    int p3;
    vector <int> p4;

    {
        // ----- test 0 -----
        int t0[] = {34, 19, 11, 60, 91, 40, 17, 50, -1, 83, 14};
        p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
        int t1[] =  {5, 0, 7, 7, 2, 10, 8, 2, 7, 1, 6, 9, 5, 10, 5, 2, 7, 2, 5, 10, 0, 2, 4, 0, 5, 5};
        p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
        int t2[] =  {2, 2, 4, 6, 7, 1, 8, 6, 0, 4, 6, 0, 7, 10, 3, 0, 2, 5, 6, 1, 2, 9, 1, 4, 10, 5};
        p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
        p3 =  320;
        int t4[] = {364, 4};
        p4.assign(t4, t4 + sizeof(t4) / sizeof(t4[0]));
        all_right = KawigiEdit_RunTest(0, p0, p1, p2, p3, true, p4) && all_right;
        // ------------------
    }

    {
        // ----- test 1 -----
        int t0[] = {0, 0, 0, 0, 0};
        p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
        int t1[] = {0};
        p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
        int t2[] = {4};
        p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
        p3 = 0;
        int t4[] = {0,1};
        p4.assign(t4, t4 + sizeof(t4) / sizeof(t4[0]));
        all_right = KawigiEdit_RunTest(1, p0, p1, p2, p3, true, p4) && all_right;
        // ------------------
    }

    {
        // ----- test 2 -----
        int t0[] = {1,2,3};
        p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
        p1.clear() /*{}*/;
        p2.clear() /*{}*/;
        p3 = 100;
        int t4[] = {5,2};
        p4.assign(t4, t4 + sizeof(t4) / sizeof(t4[0]));
        all_right = KawigiEdit_RunTest(2, p0, p1, p2, p3, true, p4) && all_right;
        // ------------------
    }

    {
        // ----- test 3 -----
        int t0[] = {1,0,-1};
        p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
        int t1[] = {0};
        p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
        int t2[] = {2};
        p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
        p3 = 0;
        p4.clear() /*{}*/;
        all_right = KawigiEdit_RunTest(3, p0, p1, p2, p3, true, p4) && all_right;
        // ------------------
    }

    {
        // ----- test 4 -----
        int t0[] = {4,2,1,0,5,6,0,3,0};
        p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
        int t1[] = {4,4,3,7,5,4,2,5,8,4};
        p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
        int t2[] = {7,3,5,0,5,4,5,0,8,3};
        p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
        p3 = 8;
        int t4[] = {14,6};
        p4.assign(t4, t4 + sizeof(t4) / sizeof(t4[0]));
        all_right = KawigiEdit_RunTest(4, p0, p1, p2, p3, true, p4) && all_right;
        // ------------------
    }

    if (all_right) {
        cout << "You're a stud (at least on the example cases)!" << endl;
    } else {
        cout << "Some of the test cases had errors." << endl;
    }
    return 0;
}
// END KAWIGIEDIT TESTING


//Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!
// kate: indent-mode cstyle; space-indent on; indent-width 0; 
